package hDOJ;

/*

2
2
3

9
21

---

红黄蓝分别对应abc
2 ==> ab,bc,ac,(算排列数共6种) + aa,bb,cc,(共3种) = 9
3 ==> abb,bcc,acc,aab,bbc,aac,(算排列数共18种) + aaa,bbb,ccc(共3种) = 21
依照前两个的步骤：1、找出所有可行的组合；2、算排列数
4 ==> abbb,bccc,accc,aabb,bbcc,aacc,aaab,bbbc,aaac(算排列数共?种) + aaaa,bbbb,cccc(共3种) = ?

这样找的话就过于复杂了
7
---

从反面出发吧
3 ==> abc的6种排列不行，其它的组合排列都行，那么就是 3 * 3 * 3 - 6 = 21
4 ==> abc的6种排列出现的情况不能出现，比如abcb是不行的，但abbc是可以的，不能出现的情况枚举出来就是
abca,abcb,abcc,aabc,babc,cabc...问题出现了，这样枚举也很复杂，比如对abc补一个c，cabc是一种情况，而这种情况也是
对cab补一个c一种情况，重复了，这样枚举就有问题

---

假设n个珠子对应的可行方法数为f(n)
如果第n-1个珠子与第n-2个珠子相同，那么第n个珠子有3种情况，那么这个条件下第n个珠子有3 * f(n-2)种情况
如果第n-1个珠子与第n-2个珠子不相同，那么第n个珠子必须与第n-1个或第n-2个相同，有2种情况，
那么这种条件下第n个珠子有2 * (f(n-1)-f(n-2))种情况
两种情况加起来就是f(n) = 2 * f(n-1) + f(n-2)

 */

import java.util.Scanner;

public class Main2569 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner scan = new Scanner(System.in);
        int C = scan.nextInt();
        while(C-- > 0) {
            int n = scan.nextInt();
            int[] f = new int[40];
            f[0] = 3;
            f[1] = 9;
            for (int i = 2; i < n; i++) {
                f[i] = 2 * f[i-1] + f[i-2];
            }
            System.out.println(f[n-1]);
        }
    }

}
